home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / ab20 / ab20_archive / utilities / printer / post-1.6src.lzh / postgraph.c < prev    next >
C/C++ Source or Header  |  1991-04-17  |  54KB  |  1,706 lines
  1. /* PostScript interpreter file "postgraph.c" - graphics routines */
  2. /* (C) Adrian Aylward 1989, 1991 */
  3.  
  4. # include "post.h"
  5.  
  6. /* Routines */
  7.  
  8. extern void checkclipsize(int size, int end);
  9. extern void setlinesize(int len);
  10. extern void flattencurve(struct point *ppoint, int depth);
  11. extern void strokeparm(struct point *ppoint, float *len);
  12. extern void strokeline(struct point *ppoint, int bjoin, int ejoin,int first);
  13. extern void strokecap(int type, int cap);
  14. extern void clipline(struct clip *pclip);
  15. extern void clipswap(struct clip *pclip);
  16. extern void swappath(int beg, int end);
  17.  
  18. /* Initialise the graphics state */
  19.  
  20. void initgstate(void)
  21. {   struct object token, *aptr;
  22.     vmref aref;
  23.     if (page.xsize > 30000 || page.ysize > 30000 || page.yheight > 30000)
  24.         error(errlimitcheck);
  25.     gstate.dev = page;
  26.     pathsize = linesize = clipsize = 0;
  27.     halfbeg = memhbeg;
  28.     halfsize = memhlen;
  29.     halfok = gstacksize + 1;
  30.     screenok = 0;
  31.     token.type = 0;
  32.     token.flags = 0;
  33.     token.length = 0;
  34.     token.value.ival = 0;
  35.     gstate.font = token;
  36.     gstate.clipbeg = 0;
  37.     aref = arrayalloc(9);
  38.     aptr = vmaptr(aref);
  39.     nametoken(&aptr[0], "dup", -1, flagexec);
  40.     nametoken(&aptr[1], "mul", -1, flagexec);
  41.     nametoken(&aptr[2], "exch", -1, flagexec);
  42.     aptr[3] = aptr[0];
  43.     aptr[4] = aptr[1];
  44.     nametoken(&aptr[5], "add", -1, flagexec);
  45.     token.type = typereal;
  46.     token.flags = 0;
  47.     token.length = 0;
  48.     token.value.rval = 1.0;
  49.     aptr[6] = token;
  50.     aptr[7] = aptr[2];
  51.     nametoken(&aptr[8], "sub", -1, flagexec);
  52.     token.type = typearray;
  53.     token.flags = flagexec;
  54.     token.length = 9;
  55.     token.value.vref = aref;
  56.     bind(&token, 0);
  57.     if (gstate.dev.depth == 4)
  58.     {   gstate.screendepth = 4;
  59.         gstate.screenangle[0] = 105.0;
  60.         gstate.screenangle[1] =  75.0;
  61.         gstate.screenangle[2] =  95.0;
  62.         gstate.screenangle[3] =  45.0;
  63.         gstate.screenfreq[0] = gstate.screenfreq[1] =
  64.             gstate.screenfreq[2] = gstate.screenfreq[3] = 60.0;
  65.         gstate.screenfunc[0] = gstate.screenfunc[1]  =
  66.             gstate.screenfunc[2] = gstate.screenfunc[3] = token;
  67.     }
  68.     else
  69.     {   gstate.screendepth = 1;
  70.         gstate.screenangle[0] = 45.0;
  71.         gstate.screenfreq[0] = 60.0;
  72.         gstate.screenfunc[0] = token;
  73.     }
  74.     gstate.transdepth = 1;
  75.     token.length = 0;
  76.     gstate.transfer[0] = token;
  77.     gstate.ucr = token;
  78.     gstate.gcr = token;
  79.     gstate.flatness = 1.0;
  80.     gstate.cacheflag = 0;
  81.     gstate.nullflag = 0;
  82.     gnest = 0;
  83.     gstack = vmallocv(sizeof (struct gstate) * (gstacksize + 1));
  84.     setuphalf();
  85.     initgraphics();
  86.     gsave();
  87.     vmstack[0].gnest = 1;
  88. }
  89.  
  90. /* Initialise the graphics */
  91.  
  92. void initgraphics(void)
  93. {   struct object token;
  94.     initctm(gstate.ctm);
  95.     gstate.pathbeg = gstate.pathend = gstate.clipbeg;
  96.     cliplength(0);
  97.     gstate.clipflag = 0;
  98.     gstate.linewidth = 1.0;
  99.     gstate.linecap = 0;
  100.     gstate.linejoin = 0;
  101.     gstate.mitrelimit = 10.0;
  102.     gstate.mitresin = 0.198997;
  103.     gstate.dashoffset = 0.0;
  104.     token.type = typearray;
  105.     token.flags = 0;
  106.     token.length = 0;
  107.     token.value.vref = 0;
  108.     gstate.dasharray = token;
  109.     gstate.gray = 0.0;
  110.     gstate.rgb[0] = gstate.rgb[1] = gstate.rgb[2] = 0.0;
  111.     gstate.rgbw[0] = gstate.rgbw[1] =
  112.         gstate.rgbw[2] = gstate.rgbw[3] = 0.0;
  113.     gstate.shadeok = 0;
  114. }
  115.  
  116. /* Initialise a matrix to the default ctm */
  117.  
  118. void initctm(float newctm[])
  119. {   newctm[0] = gstate.dev.xden / 72.0;
  120.     newctm[1] = 0.0;
  121.     newctm[2] = 0.0;
  122.     newctm[3] = gstate.dev.yden / 72.0;
  123.     newctm[4] = -gstate.dev.xoff;
  124.     newctm[5] = -gstate.dev.yoff;
  125.     if (gstate.dev.ydir < 0)
  126.     {   newctm[3] = -newctm[3];
  127.         newctm[5] = (gstate.dev.yheight + gstate.dev.yoff);
  128.     }
  129. }
  130.  
  131. /* Change device page */
  132.  
  133. void setdevice(struct device *ppage)
  134. {   struct gstate *pgstate;
  135.     int i;
  136.  
  137.     /* Check whether the densities or depth have changed; install the page */
  138.  
  139.     if (ppage->depth != page.depth ||
  140.         ppage->xden != page.xden ||
  141.         ppage->yden != page.yden ||
  142.         ppage->ydir != page.ydir)
  143.     {   halfok = gstacksize + 1;
  144.         screenok = 0;
  145.     }
  146.     page = *ppage;
  147.  
  148.     /* Update all the page devices on the gstate stack */
  149.  
  150.     i = gnest;
  151.     pgstate = &gstack[0];
  152.     for (;;)
  153.     {   if (i == 0) pgstate = &gstate;
  154.         if (!pgstate->cacheflag && !pgstate->nullflag)
  155.         {   if (page.depth != pgstate->dev.depth) pgstate->shadeok = 0;
  156.             pgstate->dev = page;
  157.         }
  158.         if (i == 0) break;
  159.         i--;
  160.         pgstate++;
  161.     }
  162.  
  163.     /* Reinitialise the CTM of the bottommost graphics state */
  164.  
  165.     initctm(gstack[0].ctm);
  166. }
  167.  
  168. /* Check the image memory size */
  169.  
  170. void checkimagesize(int len)
  171. {   if (len > memilen)
  172.     {   memfree(memibeg, memilen);
  173.         memilen = 0;
  174.         memibeg = memalloc(len);
  175.         if (memibeg == NULL) error(errmemoryallocation);
  176.         memilen = len;
  177.     }
  178. }
  179.  
  180. /* Check the line array size */
  181.  
  182. void checklinesize(int size)
  183. {   int len, segs;
  184.     if (size > linesize)
  185.     {   len = (sizeof (struct line) +
  186.                sizeof (struct line *) +
  187.                sizeof (struct lineseg) * 2) * size;
  188.         segs = (len + memlmin - 1) / memlmin;
  189.         if (segs > memlsegmax) error(errlimitcheck);
  190.         setlinesize(memlmin * segs);
  191.     }
  192. }
  193.  
  194. /* Check the clip array size, relocating the clip pointers */
  195.  
  196. void checkclipsize(int size, int end)
  197. {   struct clip *pclip, **pcptr;
  198.     int len, segs, oldsize;
  199.     if (size > clipsize)
  200.     {   oldsize = clipsize;
  201.         len = (sizeof (struct clip) +
  202.                sizeof (struct clip *)) * size;
  203.         segs = (len + memlmin - 1) / memlmin;
  204.         if (segs > memlsegmax) error(errlimitcheck);
  205.         pclip = cliparray;
  206.         setlinesize(memlmin * segs);
  207.         pcptr = (void *) (cliparray + oldsize);
  208.         while (end--)
  209.             clipptr[end] = cliparray + (pcptr[end] - pclip);
  210.     }
  211. }
  212.  
  213. /* Set the line and clip array memory size */
  214.  
  215. void setlinesize(int len)
  216. {   void *beg;
  217.     beg = memalloc(len);
  218.     if (beg == NULL) error(errmemoryallocation);
  219.     memcpy((char *) beg, (char *) memlbeg, memllen);
  220.     memfree(memlbeg, memllen);
  221.     memlbeg = beg;
  222.     memllen = len;
  223.     linesize = memllen / (sizeof (struct line) +
  224.                           sizeof (struct line *) +
  225.                           sizeof (struct lineseg) * 2);
  226.     linearray = memlbeg;
  227.     lineptr = (void *) (linearray + linesize);
  228.     linesegarray = (void *) (lineptr + linesize);
  229.     clipsize = memllen / (sizeof (struct clip) +
  230.                           sizeof (struct clip *));
  231.     cliparray = memlbeg;
  232.     clipptr = (void *) (cliparray + clipsize);
  233. }
  234.  
  235. /* Check the path array size */
  236.  
  237. void checkpathsize(int size)
  238. {   void *beg;
  239.     int len, segs;
  240.     if (size > pathsize)
  241.     {   len = sizeof (struct point) * size;
  242.         segs = (len + mempmin - 1) / mempmin;
  243.         if (segs > mempsegmax) error(errlimitcheck);
  244.         len = mempmin * segs;
  245.         beg = memalloc(len);
  246.         if (beg == NULL) error(errmemoryallocation);
  247.         memcpy((char *) beg, (char *) mempbeg, memplen);
  248.         memfree(mempbeg, memplen);
  249.         mempbeg = beg;
  250.         memplen = len;
  251.         pathsize = len / sizeof (struct point);
  252.         patharray = mempbeg;
  253.     }
  254. }
  255.  
  256. /* Shuffle the path up or down to change the clip path length */
  257.  
  258. void cliplength(int cliplen)
  259. {   struct point *ppoint1, *ppoint2;
  260.     int pathlen, len;
  261.     len = pathlen = gstate.pathend - gstate.pathbeg;
  262.     checkpathsize(gstate.clipbeg + cliplen + pathlen);
  263.     ppoint1 = &patharray[gstate.clipbeg + cliplen];
  264.     ppoint2 = &patharray[gstate.pathbeg];
  265.     if      (ppoint1 > ppoint2)
  266.     {   ppoint1 += pathlen;
  267.         ppoint2 += pathlen;
  268.         while (len--) *--ppoint1 = *--ppoint2;
  269.     }
  270.     else if (ppoint1 < ppoint2)
  271.         while (len--) *ppoint1++ = *ppoint2++;
  272.     gstate.pathbeg = gstate.clipbeg + cliplen;
  273.     gstate.pathend = gstate.pathbeg + pathlen;
  274. }
  275.  
  276. /* Get the clipping path */
  277.  
  278. void clippath(void)
  279. {   struct point point, *ppoint1, *ppoint2;
  280.     int len, l;
  281.     if (gstate.clipflag)
  282.         len = gstate.pathbeg - gstate.clipbeg;
  283.     else
  284.         len = 5;
  285.     checkpathsize(gstate.pathbeg + len);
  286.     ppoint1 = &patharray[gstate.pathbeg];
  287.     if (gstate.clipflag)
  288.     {   ppoint2 = &patharray[gstate.clipbeg];
  289.         l = len;
  290.         while (l--) *ppoint1++ = *ppoint2++;
  291.     }
  292.     else
  293.     {   point.type = ptmove;
  294.         point.x = 0.0;
  295.         point.y = 0.0;
  296.         ppoint1[0] = point;
  297.         point.type = ptclosex;
  298.         ppoint1[4] = point;
  299.         point.type = ptline;
  300.         point.x = gstate.dev.xsize;
  301.         ppoint1[1] = point;
  302.         point.y = gstate.dev.yheight;
  303.         ppoint1[2] = point;
  304.         point.x = 0.0;
  305.         ppoint1[3] = point;
  306.     }
  307.     gstate.pathend = gstate.pathbeg + len;
  308. }
  309.  
  310. /* Save the graphics state */
  311.  
  312. void gsave(void)
  313. {   struct point *ppoint1, *ppoint2;
  314.     int i;
  315.     if (istate.flags & intgraph) error(errundefined);
  316.     if (gnest == gstacksize) error(errlimitcheck);
  317.     i = gstate.pathend - gstate.clipbeg;
  318.     checkpathsize(gstate.pathend + i);
  319.     gstack[gnest++] = gstate;
  320.     if (i != 0)
  321.     {   ppoint1 = &patharray[gstate.clipbeg];
  322.         ppoint2 = &patharray[gstate.pathend];
  323.         gstate.clipbeg += i;
  324.         gstate.pathbeg += i;
  325.         gstate.pathend += i;
  326.         while (i--) *ppoint2++ = *ppoint1++;
  327.     }
  328. }
  329.  
  330. /* Restore the graphics state */
  331.  
  332. void grest(void)
  333. {   if (istate.flags & intgraph) error(errundefined);
  334.     if (gnest > istate.gbase &&
  335.         gnest > vmstack[vmnest].gnest)
  336.     {   gstate = gstack[--gnest];
  337.         if (gnest <= halfok)
  338.         {   halfok = gstacksize + 1;
  339.             setuphalf();
  340.         }
  341.     }
  342.     screenok = 0;
  343. }
  344.  
  345. /* Restore the graphics state to the previous save */
  346.  
  347. void grestall(void)
  348. {   int nest;
  349.     if (istate.flags & intgraph) error(errundefined);
  350.     nest = vmstack[vmnest].gnest;
  351.     if (nest > istate.gbase)
  352.     {   gnest = nest;
  353.         gstate = gstack[--gnest];
  354.         gsave();
  355.         if (gnest <= halfok)
  356.         {   halfok = gstacksize + 1;
  357.             setuphalf();
  358.         }
  359.         screenok = 0;
  360.     }
  361. }
  362.  
  363. /* Get a matrix */
  364.  
  365. void getmatrix(vmref aref, float *matrix)
  366. {   struct object *aptr;
  367.     int i;
  368.     i = 6;
  369.     aptr = vmaptr(aref);
  370.     while (i--)
  371.     {   if      (aptr->type == typeint)
  372.             *matrix = aptr->value.ival;
  373.         else if (aptr->type == typereal)
  374.             *matrix = aptr->value.rval;
  375.         else
  376.             error(errtypecheck);
  377.         aptr++;
  378.         matrix++;
  379.     }
  380. }
  381.  
  382. /* Put a matrix */
  383.  
  384. void putmatrix(vmref aref, float *matrix)
  385. {   struct object token, *aptr;
  386.     int i;
  387.     token.type = typereal;
  388.     token.flags = 0;
  389.     token.length = 0;
  390.     i = 6;
  391.     aptr = vmaptr(aref);
  392.     while (i--)
  393.     {   token.value.rval = *matrix++;
  394.         *aptr++ = token;
  395.     }
  396. }
  397.  
  398. /* Multiply two matrices */
  399.  
  400. void multiplymatrix(float *mat1, float *mat2, float *mat3)
  401. {   mat1[0] = mat2[0] * mat3[0] + mat2[1] * mat3[2];
  402.     mat1[1] = mat2[0] * mat3[1] + mat2[1] * mat3[3];
  403.     mat1[2] = mat2[2] * mat3[0] + mat2[3] * mat3[2];
  404.     mat1[3] = mat2[2] * mat3[1] + mat2[3] * mat3[3];
  405.     mat1[4] = mat2[4] * mat3[0] + mat2[5] * mat3[2] + mat3[4];
  406.     mat1[5] = mat2[4] * mat3[1] + mat2[5] * mat3[3] + mat3[5];
  407. }
  408.  
  409. /* Invert a matrix */
  410.  
  411. void invertmatrix(float *mat1, float *mat2)
  412. {   float d = mat2[0] * mat2[3] - mat2[1] * mat2[2];
  413.     mat1[0] =  mat2[3] / d;
  414.     mat1[1] = -mat2[1] / d;
  415.     mat1[2] = -mat2[2] / d;
  416.     mat1[3] =  mat2[0] / d;
  417.     mat1[4] = (mat2[2] * mat2[5] - mat2[3] * mat2[4]) / d;
  418.     mat1[5] = (mat2[1] * mat2[4] - mat2[0] * mat2[5]) / d;
  419. }
  420.  
  421. /* Transform a point by a matrix */
  422.  
  423. void transform(struct point *ppoint, float *matrix)
  424. {   float x, y;
  425.     x = ppoint->x;
  426.     y = ppoint->y;
  427.     ppoint->x = x * matrix[0] + y * matrix[2] + matrix[4];
  428.     ppoint->y = x * matrix[1] + y * matrix[3] + matrix[5];
  429. }
  430.  
  431. /* Delta transform a point by a matrix */
  432.  
  433. void dtransform(struct point *ppoint, float *matrix)
  434. {   float x, y;
  435.     x = ppoint->x;
  436.     y = ppoint->y;
  437.     ppoint->x = x * matrix[0] + y * matrix[2];
  438.     ppoint->y = x * matrix[1] + y * matrix[3];
  439. }
  440.  
  441. /* Inverse transform a point by a matrix */
  442.  
  443. void itransform(struct point *ppoint, float *matrix)
  444. {   float x, y, d;
  445.     x = ppoint->x;
  446.     y = ppoint->y;
  447.     d = matrix[0] * matrix[3] - matrix[1] * matrix[2];
  448.     ppoint->x = (x * matrix[3] - y * matrix[2] +
  449.         matrix[5] * matrix[2] - matrix[4] * matrix[3]) / d;
  450.     ppoint->y = (y * matrix[0] - x * matrix[1] +
  451.         matrix[4] * matrix[1] - matrix[5] * matrix[0]) / d;
  452. }
  453.  
  454. /* Inverse delta transform a point by a matrix */
  455.  
  456. void idtransform(struct point *ppoint, float *matrix)
  457. {   float x, y, d;
  458.     x = ppoint->x;
  459.     y = ppoint->y;
  460.     d = matrix[0] * matrix[3] - matrix[1] * matrix[2];
  461.     ppoint->x = (x * matrix[3] - y * matrix[2]) / d;
  462.     ppoint->y = (y * matrix[0] - x * matrix[1]) / d;
  463. }
  464.  
  465. /* Generate a circular arc */
  466.  
  467. void arc(int dir, float radaa[3],
  468.          struct point *centre, struct point *beg, struct point *end)
  469. {   struct point point[3], *ppoint;
  470.     float ang1, ang2, angd, angm, radius, radm, rh, cos1, cos2, sin1, sin2;
  471.     int num;
  472.  
  473.     /* Find out which direction, and the angle of the arc */
  474.  
  475.     radius = radaa[0];
  476.     ang1 = fmod(radaa[1], twopi);
  477.     ang2 = fmod(radaa[2], twopi);
  478.     if      (dir == 0)
  479.     {  if (fabs(ang2 - ang1) > pi)
  480.            if (ang2 > ang1)
  481.                ang1 += twopi;
  482.            else
  483.                ang2 += twopi;
  484.     }
  485.     else if (dir > 0)
  486.     {  if (ang2 < ang1 + pdelta) ang2 += twopi;
  487.     }
  488.     else
  489.        if (ang2 > ang1 + pdelta) ang1 += twopi;
  490.     angd = ang2 - ang1;
  491.  
  492.     /* Determine (a rough upper bound of) the radius, in pixels */
  493.  
  494.     radm = gstate.ctm[0];
  495.     if (gstate.ctm[1] > radm) radm = gstate.ctm[1];
  496.     if (gstate.ctm[2] > radm) radm = gstate.ctm[2];
  497.     if (gstate.ctm[3] > radm) radm = gstate.ctm[3];
  498.     radm *= radaa[0];
  499.  
  500.     /* Determine the number of Bezier curves needed to approximate the arc */
  501.  
  502.     if      (radm <= 27.0)
  503.         angm = pi       + .0001;
  504.     else if (radm <= 1834.0)
  505.         angm = pi / 2.0 + .0001;
  506.     else if (radm <= 20953.0)
  507.         angm = pi / 3.0 + .0001;
  508.     else if (radm <= 117778.0)
  509.         angm = pi / 4.0 + .0001;
  510.     else
  511.         angm = pi / 8.0 + .0001;
  512.     num = (int) ceil(fabs(angd) / angm);
  513.     angd = angd / num;
  514.  
  515.     /* Generate a move or line from the current point */
  516.  
  517.     cos2 = cos(ang1);
  518.     sin2 = sin(ang1);
  519.     point[2].type = ptmove;
  520.     point[2].x = centre->x + radius * cos2;
  521.     point[2].y = centre->y + radius * sin2;
  522.     if (dir == 0) *beg = point[2];
  523.     transform(&point[2], gstate.ctm);
  524.     pathend = gstate.pathend;
  525.     ppoint = &patharray[pathend];
  526.     if (gstate.pathbeg == pathend ||
  527.         fabs(point[2].x - (ppoint - 1)->x) >= 0.2 ||
  528.         fabs(point[2].y - (ppoint - 1)->y) >= 0.2)
  529.     {   if (gstate.pathbeg != pathend) point[2].type = ptline;
  530.         checkpathsize(pathend + 1);
  531.         patharray[pathend++] = point[2];
  532.     }
  533.     point[0].type = ptcurve;
  534.     point[1].type = ptcurve;
  535.     point[2].type = ptcurve;
  536.  
  537.     /* Loop to generate the curves */
  538.  
  539.     while (num--)
  540.     {   ang2 = ang1 + angd;
  541.         cos1 = cos2;
  542.         sin1 = sin2;
  543.         cos2 = cos(ang2);
  544.         sin2 = sin(ang2);
  545.  
  546.         /* We place the intermediate control points on the tangents at the
  547.          * endpoints (so the gradient is correct) and at a height 4/3 the
  548.          * height of the midpoint of the arc (so the midpoint of the curve
  549.          * is the same as the midpoint of the arc) */
  550.  
  551.         rh = radius * f43 * tan(angd / 4.0);
  552.         point[0].x = -rh * sin1;
  553.         point[0].y =  rh * cos1;
  554.         point[1].x =  rh * sin2;
  555.         point[1].y = -rh * cos2;
  556.         dtransform(&point[0], gstate.ctm);
  557.         dtransform(&point[1], gstate.ctm);
  558.         point[0].x += point[2].x;
  559.         point[0].y += point[2].y;
  560.  
  561.         point[2].x = centre->x + radius * cos2;
  562.         point[2].y = centre->y + radius * sin2;
  563.         if (dir == 0) *end = point[2];
  564.         transform(&point[2], gstate.ctm);
  565.         point[1].x += point[2].x;
  566.         point[1].y += point[2].y;
  567.         checkpathsize(pathend + 3);
  568.         ppoint = &patharray[pathend];
  569.         ppoint[0] = point[0];
  570.         ppoint[1] = point[1];
  571.         ppoint[2] = point[2];
  572.         pathend += 3;
  573.         ang1 = ang2;
  574.     }
  575.  
  576.     gstate.pathend = pathend;
  577. }
  578.  
  579. /* Close the current path */
  580.  
  581. void closepath(int type)
  582. {   struct point point, *ppoint;
  583.     if (gstate.pathbeg == gstate.pathend) return;
  584.     ppoint = &patharray[gstate.pathend - 1];
  585.  
  586.     /* If it is closed already, make the close explicit if necessary */
  587.  
  588.     if (ppoint->type == ptclosex)
  589.         return;
  590.     if (ppoint->type == ptclosei)
  591.     {   ppoint->type = type;
  592.         return;
  593.     }
  594.     if (ppoint->type == ptmove)
  595.         return;
  596.  
  597.     /* Scan back to the beginning of the sub path to find the coordinates to
  598.      * close it to */
  599.  
  600.     for (;;)
  601.     {   point = *ppoint;
  602.         if (point.type == ptclosex ||
  603.             point.type == ptclosei ||
  604.             point.type == ptmove)
  605.             break;
  606.         ppoint--;
  607.     }
  608.  
  609.     /* Append a close */
  610.  
  611.     point.type = type;
  612.     checkpathsize(gstate.pathend + 1);
  613.     patharray[gstate.pathend++] = point;
  614.     return;
  615. }
  616.  
  617. /* Flatten the current path */
  618.  
  619. void flattenpath(void)
  620. {   struct point point[4], *ppoint1, *ppoint2;
  621.     int len, num;
  622.  
  623.     len = gstate.pathend - gstate.pathbeg;
  624.  
  625.     /* Skip all elements before the first curve */
  626.  
  627.     ppoint1 = &patharray[gstate.pathbeg];
  628.     for (;;)
  629.     {   if (len == 0) return;
  630.         if (ppoint1->type == ptcurve) break;
  631.         ppoint1++;
  632.         len--;
  633.     }
  634.  
  635.     num = len;
  636.     pathbeg = pathend = gstate.pathend;
  637.  
  638.     /* Flatten curves, copying all points into workspace at the end of the
  639.      * path array */
  640.  
  641.     for (;;)
  642.     {   if (len == 0) break;
  643.         ppoint1 = &patharray[pathbeg - len];
  644.         point[1] = ppoint1[0];
  645.         if (point[1].type == ptcurve)
  646.         {   point[0] = ppoint1[-1];
  647.             point[2] = ppoint1[1];
  648.             point[3] = ppoint1[2];
  649.             flattencurve(point, 0);
  650.             len -= 3;
  651.         }
  652.         else
  653.         {   checkpathsize(pathend + 1);
  654.             patharray[pathend++] = point[1];
  655.             len--;
  656.         }
  657.     }
  658.  
  659.     /* Copy the workspace back to the path */
  660.  
  661.     ppoint1 = &patharray[gstate.pathend - num];
  662.     ppoint2 = &patharray[pathbeg];
  663.     len = pathend - pathbeg;
  664.     gstate.pathend += len - num;
  665.     while (len--) *ppoint1++ = *ppoint2++;
  666. }
  667.  
  668. /* Flatten a curve */
  669.  
  670. void flattencurve(struct point *ppoint, int depth)
  671. {   struct point point, curves[7];
  672.     float f, g, h, a, b, c;
  673.  
  674.     /* Find the flatness of the curve.  As it lies within the convex hull
  675.      * of its control points we just find the maximum distance of the
  676.      * intermediate control points from the straight line joining the ends */
  677.  
  678.     a = ppoint[3].y - ppoint[0].y;
  679.     b = ppoint[0].x - ppoint[3].x;
  680.     c = ppoint[3].x * ppoint[0].y - ppoint[0].x * ppoint[3].y;
  681.     f = a * ppoint[1].x + b * ppoint[1].y + c;
  682.     f = f * f;
  683.     g = a * ppoint[2].x + b * ppoint[2].y + c;
  684.     g = g * g;
  685.     h = gstate.flatness * gstate.flatness * (a * a + b * b);
  686.  
  687.     /* If the curve is not flat enough bisect it and flatten the halves */
  688.  
  689.     if (f > h || g > h)
  690.     {   point.type = ptcurve;
  691.         curves[0] = ppoint[0];
  692.         point.x = ppoint[0].x * f12 + ppoint[1].x * f12;
  693.         point.y = ppoint[0].y * f12 + ppoint[1].y * f12;
  694.         curves[1] = point;
  695.         point.x = ppoint[0].x * f14 + ppoint[1].x * f12 + ppoint[2].x * f14;
  696.         point.y = ppoint[0].y * f14 + ppoint[1].y * f12 + ppoint[2].y * f14;
  697.         curves[2] = point;
  698.         point.x = ppoint[0].x * f18 + ppoint[1].x * f38 + ppoint[2].x * f38
  699.                 + ppoint[3].x * f18;
  700.         point.y = ppoint[0].y * f18 + ppoint[1].y * f38 + ppoint[2].y * f38
  701.                 + ppoint[3].y * f18;
  702.         curves[3] = point;
  703.         point.x = ppoint[1].x * f14 + ppoint[2].x * f12 + ppoint[3].x * f14;
  704.         point.y = ppoint[1].y * f14 + ppoint[2].y * f12 + ppoint[3].y * f14;
  705.         curves[4] = point;
  706.         point.x = ppoint[2].x * f12 + ppoint[3].x * f12;
  707.         point.y = ppoint[2].y * f12 + ppoint[3].y * f12;
  708.         curves[5] = point;
  709.         curves[6] = ppoint[3];
  710.         if (depth == maxdepth) error(errlimitcheck);
  711.         flattencurve(&curves[0], depth + 1);
  712.         flattencurve(&curves[3], depth + 1);
  713.     }
  714.  
  715.     /* Otherwise make it a straight line */
  716.  
  717.     else
  718.     {   point = ppoint[3];
  719.         point.type = ptline;
  720.         checkpathsize(pathend + 1);
  721.         patharray[pathend++] = point;
  722.     }
  723. }
  724.  
  725. /* Create a stroke path; return it or fill it */
  726.  
  727. void strokepath(int fillflag)
  728. {   struct point *ppoint1, *ppoint2;
  729.     float length;
  730.     int pti, len, ln2, bjoin, ejoin, sjoin, first, next, lev;
  731.  
  732.     lev = flushlevel(-1);
  733.  
  734.     /* Loop through the path ... */
  735.  
  736.     pathbeg = pathend = gstate.pathend;
  737.     len = gstate.pathend - gstate.pathbeg;
  738.     pti = gstate.pathbeg;
  739.     sjoin = bjoin = -1;
  740.     first = 1;
  741.  
  742.     while (len--)
  743.     {   ppoint1 = &patharray[pti];
  744.  
  745.         /* If it is a line or an explicit close we stroke it ... */
  746.  
  747.         if (ppoint1->type == ptline || ppoint1->type == ptclosex)
  748.         {
  749.             /* If it is a line we scan the subpath to see if its end is
  750.              * joined to a line or explicit close following; if it is the
  751.              * first line we scan to the end of the subpath to see if there
  752.              * is an explicit close that is joined to its beginning, setting
  753.              * up its parameters, and saving the joint for use we get to the
  754.              * close. */
  755.  
  756.             if (ppoint1->type == ptline)
  757.             {   ln2 = len;
  758.                 ppoint2 = ppoint1;
  759.                 ejoin = -1;
  760.                 while (ln2--)
  761.                 {   ppoint2++;
  762.                     if (ppoint2->type == ptline || ppoint2->type == ptclosex)
  763.                     {   if (ppoint2 == (ppoint1 + 1))
  764.                             ejoin = gstate.linejoin;
  765.                     }
  766.                     else
  767.                         break;
  768.                     if (first)
  769.                     {   if (ppoint2->type == ptclosex)
  770.                         {   strokeparm(ppoint2, &length);
  771.                             sjoin = bjoin = gstate.linejoin;
  772.                             break;
  773.                         }
  774.                     }
  775.                     else
  776.                         break;
  777.                 }
  778.                 next = 0;
  779.             }
  780.  
  781.  
  782.             /* If it is a close we use the end join we saved. */
  783.  
  784.             else
  785.             {   ejoin = sjoin;
  786.                 sjoin = -1;
  787.                 next = 1;
  788.             }
  789.  
  790.             /* Stroke the line or close.  The end joint begins the next
  791.              * line */
  792.  
  793.             strokeline(ppoint1, bjoin, ejoin, first);
  794.             bjoin = ejoin;
  795.             first = next;
  796.  
  797.             /* If we are filling, do it now and discard the path */
  798.  
  799.             if (fillflag)
  800.             {   fill(pathbeg, pathend, -1);
  801.                 pathend = pathbeg;
  802.             }
  803.  
  804.         }
  805.  
  806.         /* Moves and implicit closes are not stroked */
  807.  
  808.         else
  809.         {   sjoin = bjoin = -1;
  810.             first = 1;
  811.         }
  812.  
  813.         pti++;
  814.     }
  815.  
  816.     /* If we are not filling, copy the stroke path to the current path */
  817.  
  818.     if (!fillflag)
  819.     {   len = pathend - pathbeg;
  820.         gstate.pathend = gstate.pathbeg + len;
  821.         ppoint1 = &patharray[gstate.pathbeg];
  822.         ppoint2 = &patharray[pathbeg];
  823.         while (len--) *ppoint1++ = *ppoint2++;
  824.     }
  825.  
  826.     flushlevel(lev);
  827. }
  828.  
  829. /* Static variables for line parameters */
  830.  
  831. static struct point cvpt; /* line Vector,                    device space */
  832. static struct point cupt; /* line Unit vector,               user space */
  833. static struct point crpt; /* line Right half width vector,   device space */
  834. static struct point cfpt; /* line Forward half width vector, device space */
  835. static struct point pvpt; /* values of the above for the previous line */
  836. static struct point pupt; /*    ..   */
  837. static struct point prpt; /*    ..   */
  838. static struct point cppt; /* current point */
  839. static struct point eppt; /* end point */
  840.  
  841. /* Stroke set up line parameters */
  842.  
  843. void strokeparm(struct point *ppoint, float *len)
  844. {   float length, d;
  845.  
  846.     /* Save the values for the previous line */
  847.  
  848.     pvpt = cvpt;
  849.     pupt = cupt;
  850.     prpt = crpt;
  851.  
  852.     /* Inverse delta transform the line to user space.  Determine its
  853.      * length */
  854.  
  855.     cupt.x = cvpt.x = ppoint[0].x - ppoint[-1].x;
  856.     cupt.y = cvpt.y = ppoint[0].y - ppoint[-1].y;
  857.     idtransform(&cupt, gstate.ctm);
  858.     *len = length = sqrt(cupt.x * cupt.x + cupt.y * cupt.y);
  859.  
  860.     /* If the length is zero the direction is arbitrary, so we choose the x
  861.      * direction (used for round line caps only.  We then return, as we
  862.      * cannot meaningly set up the remaining parameters */
  863.  
  864.     if (length == 0.0)
  865.     {   cupt.x = 1.0;
  866.         cupt.y = 0.0;
  867.         return;
  868.     }
  869.  
  870.     /* Construct a unit vector along the line */
  871.  
  872.     cupt.x /= length;
  873.     cupt.y /= length;
  874.  
  875.     /* Construct vectors along the line (forward) and across the line (right)
  876.      * of length equal to half the line width.  Then transform them back to
  877.      * device space. */
  878.  
  879.     d = gstate.linewidth / 2.0;
  880.     cfpt.x =  cupt.x * d;
  881.     cfpt.y =  cupt.y * d;
  882.     crpt.x =  cfpt.y;
  883.     crpt.y = -cfpt.x;
  884.     dtransform(&cfpt, gstate.ctm);
  885.     dtransform(&crpt, gstate.ctm);
  886. }
  887.  
  888. /* Static variables for dash lengths */
  889.  
  890. static int dashcnt, dashsub;
  891. static float dashlength;
  892.  
  893. /* Stroke a line */
  894.  
  895. void strokeline(struct point *ppoint, int bjoin, int ejoin, int first)
  896. {   struct point point;
  897.     float x, y, xx, yy, h, s, c, d;
  898.     float linelen, length, segment;
  899.     int join;
  900.  
  901.     /* If this is the first line in the subpath initialise our location in
  902.      * the dash array */
  903.  
  904.     if (first)
  905.     {   dashcnt = 0;
  906.         if (gstate.dasharray.length != 0)
  907.         {   length = gstate.dashoffset;
  908.             dashsub = 0;
  909.             for (;;)
  910.             {   dashlength = gstate.dashlength[dashsub];
  911.                 if (dashlength > length)
  912.                 {   dashlength -= length;
  913.                     break;
  914.                 }
  915.                 length -= dashlength;
  916.                 dashcnt++;
  917.                 dashsub++;
  918.                 if (dashsub == gstate.dasharray.length) dashsub = 0;
  919.             }
  920.         }
  921.     }
  922.  
  923.     /* Set up the parameters.  Lines of zero length are ignored - unless
  924.        they have round caps, in which case we just make two caps */
  925.  
  926.     strokeparm(ppoint, &length);
  927.     linelen = length;
  928.     if (length == 0.0)
  929.     {   if (gstate.linecap != 1) return;
  930.         bjoin = -1;
  931.         ejoin = -1;
  932.     }
  933.  
  934.     /* Start at the beginning of the line */
  935.  
  936.     join = bjoin;
  937.     cppt = ppoint[-1];
  938.     eppt = ppoint[0];
  939.  
  940.     /* Loop stroking segments according to the dash pattern */
  941.  
  942.     for (;;)
  943.     {
  944.         /* Find the length remaining in the current dash */
  945.  
  946.         segment = length;
  947.         if (gstate.dasharray.length != 0)
  948.         {   if (dashlength == 0.0)
  949.             {   dashcnt++;
  950.                 dashsub++;
  951.                 if (dashsub == gstate.dasharray.length) dashsub = 0;
  952.                 dashlength = gstate.dashlength[dashsub];
  953.             }
  954.             if (dashlength >= length)
  955.             {   segment = length;
  956.                 dashlength -= length;
  957.             }
  958.             else
  959.             {   segment = dashlength;
  960.                 dashlength = 0.0;
  961.             }
  962.         }
  963.  
  964.         /* Only draw the segment if we are in a dash */
  965.  
  966.         if ((dashcnt & 1) == 0)
  967.         {   pathseg = pathend;
  968.  
  969.             /* If the line begins with a mitred or beveled join calculate the
  970.              * cross product of the previous and current line vectors; this
  971.              * is the sine of the angle between them, and tells us which side
  972.              * to make the joint on.  If we have a mitred join we must check
  973.              * the mitre limit; first we check the dot product of the unit
  974.              * vectors to see if the angle is less than a right angle; then
  975.              * we check the cross product (sine of the angle) against the
  976.              * mitre limit.  We don't make mitred joins is the angle is very
  977.              * small, as we would divide by zero. */
  978.  
  979.             if (join == 0 || join == 2)
  980.             {   s = pupt.x * cupt.y - pupt.y * cupt.x;
  981.                 if (join == 0)
  982.                 {   c = pupt.x * cupt.x + pupt.y * cupt.y;
  983.                     d = pvpt.x * cvpt.y - cvpt.x * pvpt.y;
  984.                     if ((gstate.mitrelimit > sqrt2) ?
  985.                             (c < 0.0 && fabs(s) < gstate.mitresin) :
  986.                             (c < 0.0 || fabs(s) > gstate.mitresin))
  987.                         join = 2;
  988.                     if (fabs(d) < 0.0001)
  989.                         join = 2;
  990.                 }
  991.  
  992.                 /* Make a mitred join.  We make the mitre on one side if
  993.                  * the angle is less than a right angle, on both if it is
  994.                  * greater */
  995.  
  996.                 if (join == 0)
  997.                 {   d = pvpt.x * cvpt.y - cvpt.x * pvpt.y;
  998.                     h = (prpt.x * pvpt.y - prpt.y * pvpt.x) / d;
  999.                     if (s > 0.0) h = -h;
  1000.                     x = cppt.x + cvpt.x * h;
  1001.                     y = cppt.y + cvpt.y * h;
  1002.                     h = (crpt.y * cvpt.x - crpt.x * cvpt.y) / d;
  1003.                     xx = pvpt.x * h;
  1004.                     yy = pvpt.y * h;
  1005.                     point.type = ptmove;
  1006.                     if (c < 0.0)
  1007.                     {   checkpathsize(pathend + 2);
  1008.                         point.x = x - xx;
  1009.                         point.y = y - yy;
  1010.                         patharray[pathend++] = point;
  1011.                         point.type = ptline;
  1012.                         point.x = x + xx;
  1013.                         point.y = y + yy;
  1014.                         patharray[pathend++] = point;
  1015.                     }
  1016.                     else
  1017.                     {   checkpathsize(pathend + 3);
  1018.                         if (s < 0.0)
  1019.                         {   point.x = cppt.x + crpt.x;
  1020.                             point.y = cppt.y + crpt.y; 
  1021.                             patharray[pathend++] = point;
  1022.                             point.type = ptline;
  1023.                             point.x = cppt.x - prpt.x;
  1024.                             point.y = cppt.y - prpt.y;
  1025.                             patharray[pathend++] = point;
  1026.                             point.x = x + xx;
  1027.                             point.y = y + yy;
  1028.                             patharray[pathend++] = point;
  1029.                         }
  1030.                         else
  1031.                         {   point.x = x - xx;
  1032.                             point.y = y - yy;
  1033.                             patharray[pathend++] = point;
  1034.                             point.type = ptline;
  1035.                             point.x = cppt.x + prpt.x;
  1036.                             point.y = cppt.y + prpt.y; 
  1037.                             patharray[pathend++] = point;
  1038.                             point.x = cppt.x - crpt.x;
  1039.                             point.y = cppt.y - crpt.y;
  1040.                             patharray[pathend++] = point;
  1041.                         }
  1042.                     }
  1043.                 }
  1044.  
  1045.                 /* Make a beveled join */
  1046.  
  1047.                 else
  1048.                 {   checkpathsize(pathend + 3);
  1049.                     point.type = ptmove;
  1050.                     point.x = cppt.x + crpt.x;
  1051.                     point.y = cppt.y + crpt.y;
  1052.                     patharray[pathend++] = point;
  1053.                     point.type = ptline;
  1054.                     if (s != 0.0)
  1055.                     {   point.x = cppt.x;
  1056.                         point.y = cppt.y;
  1057.                         if (s < 0.0)
  1058.                         {   point.x -= prpt.x;
  1059.                             point.y -= prpt.y;
  1060.                         }
  1061.                         else
  1062.                         {   point.x += prpt.x;
  1063.                             point.y += prpt.y;
  1064.                         }
  1065.                         patharray[pathend++] = point;
  1066.                     }
  1067.                     point.x = cppt.x - crpt.x;
  1068.                     point.y = cppt.y - crpt.y;
  1069.                     patharray[pathend++] = point;
  1070.                 }
  1071.             }
  1072.  
  1073.             else
  1074.  
  1075.                 /* Make a round join (like a round cap) or a cap */
  1076.  
  1077.                 strokecap(ptmove, (join == 1) ? 1 : gstate.linecap);
  1078.         }
  1079.  
  1080.         /* The end of the line */
  1081.  
  1082.         if (segment == length)
  1083.         {   join = ejoin;
  1084.             cppt = eppt;
  1085.         }
  1086.         else
  1087.         {   join = -1;
  1088.             s = segment / linelen;
  1089.             cppt.x += cvpt.x * s;
  1090.             cppt.y += cvpt.y * s;
  1091.         }
  1092.  
  1093.         if ((dashcnt & 1) == 0)
  1094.         {
  1095.  
  1096.             /* If the line ends with a join make a butt cap, otherwise end
  1097.              * with the line cap */
  1098.  
  1099.             strokecap(ptline, (join >= 0) ? 0 : gstate.linecap);
  1100.  
  1101.             /* Close the path */
  1102.  
  1103.             point = patharray[pathseg];
  1104.             point.type = ptclosex;
  1105.             checkpathsize(pathend + 1);
  1106.             patharray[pathend++] = point;
  1107.         }
  1108.  
  1109.         join = -1;
  1110.         length -= segment;
  1111.         if (length == 0.0) break;
  1112.     }
  1113. }
  1114.  
  1115. /* Stroke a line cap */
  1116.  
  1117. void strokecap(int type, int cap)
  1118. {   struct point points[7];
  1119.     float fx, fy, rx, ry;
  1120.  
  1121.     /* At the beginning caps face the opposite way to the end */
  1122.  
  1123.     if (type == ptmove)
  1124.     {   fx = -cfpt.x;
  1125.         fy = -cfpt.y;
  1126.         rx = -crpt.x;
  1127.         ry = -crpt.y;
  1128.     }
  1129.     else
  1130.     {   fx =  cfpt.x;
  1131.         fy =  cfpt.y;
  1132.         rx =  crpt.x;
  1133.         ry =  crpt.y;
  1134.     }
  1135.  
  1136.     points[0].type = type;
  1137.     points[0].x = cppt.x - rx;
  1138.     points[0].y = cppt.y - ry;
  1139.     points[6].type = ptline;
  1140.     points[6].x = cppt.x + rx;
  1141.     points[6].y = cppt.y + ry;
  1142.  
  1143.     /* Butt cap */
  1144.  
  1145.     if      (cap == 0)
  1146.     {   checkpathsize(pathend + 2);
  1147.         patharray[pathend++] = points[0];
  1148.         patharray[pathend++] = points[6];
  1149.     }
  1150.  
  1151.     /* Projecting square cap */
  1152.  
  1153.     else if (cap == 2)
  1154.     {   points[0].x += fx;
  1155.         points[0].y += fy;
  1156.         points[6].x += fx;
  1157.         points[6].y += fy;
  1158.         checkpathsize(pathend + 2);
  1159.         patharray[pathend++] = points[0];
  1160.         patharray[pathend++] = points[6];
  1161.     }
  1162.  
  1163.     /* Round cap.  Construct a Bezier curve approximation (in 2 sections) and
  1164.      * flatten it.  We always use two sections because they are faster to
  1165.      * construct than to flatten */
  1166.  
  1167.     else
  1168.     {   points[3].type = ptcurve;
  1169.         points[3].x = cppt.x + fx;
  1170.         points[3].y = cppt.y + fy;
  1171.         fx *= f43rt2;
  1172.         fy *= f43rt2;
  1173.         rx *= f43rt2;
  1174.         ry *= f43rt2;
  1175.         points[1] = points[0];
  1176.         points[1].x += fx;
  1177.         points[1].y += fy;
  1178.         points[2] = points[3];
  1179.         points[2].x -= rx;
  1180.         points[2].y -= ry;
  1181.         points[4] = points[3];
  1182.         points[4].x += rx;
  1183.         points[4].y += ry;
  1184.         points[5] = points[6];
  1185.         points[5].x += fx;
  1186.         points[5].y += fy;
  1187.         checkpathsize(pathend + 1);
  1188.         patharray[pathend++] = points[0];
  1189.         flattencurve(&points[0], 0);
  1190.         flattencurve(&points[3], 0);
  1191.     }
  1192. }
  1193.  
  1194. /* Make a new clipping path by intersecting it with the current path */
  1195.  
  1196. void clip(int rule)
  1197. {   struct point point, *ppoint;
  1198.     struct clip clip1, clip2, *pclip1, *pclip2, *pclipx;
  1199.     double a1, b1, c1, a2, b2, c2;
  1200.     double l1, l2, l3;
  1201.     double h11, h12, h21, h22, hh;
  1202.     int xx, yy, x1, y1;
  1203.     int count, count1, count2, step;
  1204.     int clipold, clipnew, clipmax, clipflg;
  1205.     int cdir1, cdir2, fdir1, fdir2;
  1206.  
  1207.     /* Set up the default clip path */
  1208.  
  1209.     if (!gstate.clipflag)
  1210.     {   cliplength(5);
  1211.         gstate.pathbeg = gstate.clipbeg;
  1212.         count = gstate.pathend;
  1213.         clippath();
  1214.         gstate.pathbeg = gstate.pathend;
  1215.         gstate.pathend = count;
  1216.     }
  1217.  
  1218.     /* Set up the clip array.  We convert the coordinates to fixed point,
  1219.      * with a scale factor of 256.  Then when we come to multiplying the
  1220.      * values to calculate the intersections it will fit into 48 bits or
  1221.      * so, a reasonable minimum accuracy for double precision floating
  1222.      * point */
  1223.  
  1224.     clipend = 0;
  1225.     for (count1 = gstate.clipbeg; count1 < gstate.pathend; count1++)
  1226.     {   ppoint = &patharray[count1];
  1227.         if (ppoint->type != ptmove)
  1228.         {   if (count1 < gstate.pathbeg)
  1229.             {   clip1.cdir = 1;
  1230.                 clip1.fdir = 0;
  1231.             }
  1232.             else
  1233.             {   clip1.cdir = 0;
  1234.                 clip1.fdir = 1;
  1235.             }
  1236.             clip1.flag = 0;
  1237.             clip1.swap = 0;
  1238.             clip1.x1 = floor(ppoint[-1].x * 256.0f + 0.5);
  1239.             clip1.y1 = floor(ppoint[-1].y * 256.0f + 0.5);
  1240.             clip1.x2 = floor(ppoint[0].x * 256.0f + 0.5);
  1241.             clip1.y2 = floor(ppoint[0].y * 256.0f + 0.5);
  1242.             clipline(&clip1);
  1243.         }
  1244.     }
  1245.  
  1246.     /* Split the lines whenever they intersect.  Owing to rounding errors
  1247.      * The resulting new lines are not in exactly the same place as before,
  1248.      * so we loop checking for intersections until we don't find any more
  1249.      */
  1250.  
  1251.     clipnew = 0;
  1252.     for (;;)
  1253.     {
  1254.         /* Shell sort the array in order of y1 */
  1255.  
  1256.         count = clipend;
  1257.         for (;;)
  1258.         {   count = count / 3 + 1;
  1259.             for (count1 = count; count1 < clipend; count1++)
  1260.                 for (count2 = count1 - count;
  1261.                      count2 >= 0 &&
  1262.                          clipptr[count2]->y1 > clipptr[count2 + count]->y1;
  1263.                      count2 -= count)
  1264.                 {    pclip1 = clipptr[count2];
  1265.                      clipptr[count2] = clipptr[count2 + count];
  1266.                      clipptr[count2 + count] = pclip1;
  1267.                 }
  1268.             if (count == 1) break;
  1269.         }
  1270.  
  1271.         /* Exit (with the array sorted) if we have no new lines */
  1272.  
  1273.         if (clipnew == clipend) break;
  1274.  
  1275.         /* Locate all the intersections for each line */
  1276.  
  1277.         count1 = 0;
  1278.         clipnew = clipend;
  1279.         while (count1 < clipend - 1)
  1280.         {   count2 = count1;
  1281.  
  1282.             /* We don't need to check for intersections with the new lines
  1283.              * we created by intersecting with ours */
  1284.  
  1285.             clipmax = clipend - 1;
  1286.             while (count2 < clipmax)
  1287.             {   count2++;
  1288.                 pclip1 = clipptr[count1];
  1289.                 pclip2 = clipptr[count2];
  1290.  
  1291.                 /* When we get to the first line whose y1 is greater than
  1292.                  * our y2 we can skip all the way to the beginning of the
  1293.                  * new lines */
  1294.  
  1295.                 if (pclip2->y1 > pclip1->y2)
  1296.                 {   if (count2 < clipnew) count2 = clipnew;
  1297.                     continue;
  1298.                 }
  1299.  
  1300.                 /* Skip lines whose bounding boxes do not intersect ours */
  1301.  
  1302.                 if (pclip2->y2 < pclip1->y1)
  1303.                     continue;
  1304.                 if (min(pclip1->x1,pclip1->x2) > max(pclip2->x1,pclip2->x2))
  1305.                     continue;
  1306.                 if (max(pclip1->x1,pclip1->x2) < min(pclip2->x1,pclip2->x2))
  1307.                     continue;
  1308.  
  1309.                 /* If the two endpoints of each line are on opposite sides
  1310.                  * of the other line, the lines must intersect.  If one is
  1311.                  * on the line but not the other, they intersect at the end.
  1312.                  * If both are on the line they are colinear.  The distance
  1313.                  * from a point (x,y) to a line (a*X +b*Y + c = 0) is given
  1314.                  * by (a*x + b*y *c) / sqrt(a**2 + b**2).  We don't bother
  1315.                  * with the square root as we only want to know the
  1316.                  * relative distances.  The test is exact as long as the
  1317.                  * numbers (integer values) we are using are not too big to
  1318.                  * be represented exactly in double precision floating point
  1319.                  */
  1320.  
  1321.                 clip1 = *pclip1;
  1322.                 clip2 = *pclip2;
  1323.                 a1 = clip1.y2 - clip1.y1;
  1324.                 b1 = clip1.x2 - clip1.x1;
  1325.                 c1 = (double) clip1.x2 * (double) clip1.y1 -
  1326.                      (double) clip1.x1 * (double) clip1.y2;
  1327.                 h11 = a1 * clip2.x1 - b1 * clip2.y1 + c1;
  1328.                 h12 = a1 * clip2.x2 - b1 * clip2.y2 + c1;
  1329.                 if (h11 > 0.0 && h12 > 0.0) continue;
  1330.                 if (h11 < 0.0 && h12 < 0.0) continue;
  1331.  
  1332.                 a2 = clip2.y2 - clip2.y1;
  1333.                 b2 = clip2.x2 - clip2.x1;
  1334.                 c2 = (double) clip2.x2 * (double) clip2.y1 -
  1335.                      (double) clip2.x1 * (double) clip2.y2;
  1336.                 h21 = a2 * clip1.x1 - b2 * clip1.y1 + c2;
  1337.                 h22 = a2 * clip1.x2 - b2 * clip1.y2 + c2;
  1338.                 if (h21 > 0.0 && h22 > 0.0) continue;
  1339.                 if (h21 < 0.0 && h22 < 0.0) continue;
  1340.  
  1341.                 /* If the lines are colinear we treat them as intersecting
  1342.                  * at the endpoints.  To find out what order the endpoints
  1343.                  * lie in, we take the beginning of line 1 as our origin
  1344.                  * and calculate the dot products of the displacements of
  1345.                  * the other endpoints with line 1 itself.  We then split
  1346.                  * the lines, knowing that the two lines must be in the
  1347.                  * same direction, as we made sure y1 < y2 or x1 < x2
  1348.                  */
  1349.  
  1350.                 if (h11 == 0.0 && h12 == 0.0)
  1351.                 {   l1 = b1 * b1 + a1 * a1;
  1352.                     l2 = (clip2.x1 - clip1.x1) * b1 +
  1353.                          (clip2.y1 - clip1.y1) * a1;
  1354.                     l3 = (clip2.x2 - clip1.x1) * b1 +
  1355.                          (clip2.y2 - clip1.y1) * a1;
  1356.  
  1357.                     if      (l2 < 0 && l3 < l1)
  1358.                     {   clip1.x2 = pclip1->x1 = clip2.x2;
  1359.                         clip1.y2 = pclip1->y1 = clip2.y2;
  1360.                         clip2.x1 = pclip2->x2 = clip1.x1;
  1361.                         clip2.y1 = pclip2->y2 = clip1.y1;
  1362.                     }
  1363.                     else if (l2 <= 0 && l3 >= l1)
  1364.                     {   clip1 = clip2;
  1365.                         clip1.x2 = pclip2->x1 = pclip1->x1;
  1366.                         clip1.y2 = pclip2->y1 = pclip1->y1;
  1367.                         clip2.x1 = pclip2->x2 = pclip1->x2;
  1368.                         clip2.y1 = pclip2->y2 = pclip1->y2;
  1369.                     }
  1370.                     else if (l2 >= 0 && l3 <= l1)
  1371.                     {   clip2 = clip1;
  1372.                         clip1.x2 = pclip1->x1 = pclip2->x1;
  1373.                         clip1.y2 = pclip1->y1 = pclip2->y1;
  1374.                         clip2.x1 = pclip1->x2 = pclip2->x2;
  1375.                         clip2.y1 = pclip1->y2 = pclip2->y2;
  1376.                     }
  1377.                     else if (l2 > 0 && l3 > l1)
  1378.                     {   clip1.x1 = pclip1->x2 = clip2.x1;
  1379.                         clip1.y1 = pclip1->y2 = clip2.y1;
  1380.                         clip2.x2 = pclip2->x1 = clip1.x2;
  1381.                         clip2.y2 = pclip2->y1 = clip1.y2;
  1382.                     }
  1383.                     clipline(&clip1);
  1384.                     clipline(&clip2);
  1385.                 }
  1386.  
  1387.                 /* Otherwise calculate the intersection */
  1388.  
  1389.                 else
  1390.                 {   hh = h22 - h21;
  1391.                     xx = floor((clip1.x1 * h22 - clip1.x2 * h21) / hh + 0.5);
  1392.                     yy = floor((clip1.y1 * h22 - clip1.y2 * h21) / hh + 0.5);
  1393.                     if (xx != clip1.x1 || yy != clip1.y1)
  1394.                     {   pclip1->x2 = clip1.x1 = xx;
  1395.                         pclip1->y2 = clip1.y1 = yy;
  1396.                         clipline(&clip1);
  1397.                     }
  1398.                     pclip2 = clipptr[count2];
  1399.                     if (xx != clip2.x1 || yy != clip2.y1)
  1400.                     {   pclip2->x2 = clip2.x1 = xx;
  1401.                         pclip2->y2 = clip2.y1 = yy;
  1402.                         clipline(&clip2);
  1403.                     }
  1404.                 }
  1405.  
  1406.                 /* We must check the directions in case of rounding error */
  1407.  
  1408.                 clipswap(clipptr[count1]);
  1409.                 clipswap(clipptr[count2]);
  1410.             }
  1411.             count1++;
  1412.         }
  1413.     }
  1414.  
  1415.     /* Count the winding number for each line.  We construct a test line
  1416.      * running horizontally from the left, at a height just greater than y1.
  1417.      * (If the line is horizontal, we regard the test line as being bent at
  1418.      * the end so it meets the line just to the right of x1.)  If we find
  1419.      * any lines colinear with ours we chain them together */
  1420.  
  1421.     count1 = 0;
  1422.     clipold = 0;
  1423.     clipflg = 0;
  1424.     while (count1 < clipend)
  1425.     {   pclip1 = clipptr[count1++];
  1426.         if (pclip1->flag != 0) continue;
  1427.  
  1428.         count2 = clipold;
  1429.         cdir1 = fdir1 = 0;
  1430.         cdir2 = pclip1->cdir;
  1431.         fdir2 = pclip1->fdir;
  1432.         pclipx = NULL;
  1433.  
  1434.         /* Scan the other lines for intersections with the test line */
  1435.  
  1436.         while (count2 < clipend)
  1437.         {   pclip2 = clipptr[count2];
  1438.             count2++;
  1439.             if (pclip2 == pclip1) continue;
  1440.  
  1441.             /* If y2 is less than our y1 we won't need to scan the line
  1442.              * again.  Swap it to the beginning and step past it next time */
  1443.  
  1444.             if (pclip2->y2 < pclip1->y1)
  1445.             {   clipptr[count2 - 1]  = clipptr[clipold];
  1446.                 clipptr[clipold] = pclip2;
  1447.                 clipold++;
  1448.                 continue;
  1449.             }
  1450.  
  1451.             /* Stop scanning when y1 is greater than ours */
  1452.  
  1453.             if (pclip2->y1 > pclip1->y1) break;
  1454.  
  1455.             /* If its y2 is greater than our y1, then if it passes to the
  1456.              * left of our x1 it must intersect the test line */
  1457.  
  1458.             if (pclip2->y2 > pclip1->y1)
  1459.             {   a1 = pclip2->x1 * (double) (pclip2->y2 - pclip1->y1) +
  1460.                      pclip2->x2 * (double) (pclip1->y1 - pclip2->y1);
  1461.                 a2 = pclip1->x1 * (double) (pclip2->y2 - pclip2->y1);
  1462.  
  1463.                 if      (a1 < a2)
  1464.                 {   cdir1 += pclip2->cdir;
  1465.                     fdir1 += pclip2->fdir;
  1466.                 }
  1467.  
  1468.             /* If it passes through our x1 we have to compare the slopes.
  1469.              * The cross procuct is the sine of the angle between them.  If
  1470.              * its slope is greater than ours it must intersect the test
  1471.              * line.  If the slopes are the same they must be colinar;
  1472.              * calculate the winding number for the far side of the line
  1473.              * and chain it */
  1474.  
  1475.                 else if (a1 == a2)
  1476.                 {   hh = (double) (pclip1->x2 - pclip1->x1) *
  1477.                          (double) (pclip2->y2 - pclip2->y1) -
  1478.                          (double) (pclip2->x2 - pclip2->x1) *
  1479.                          (double) (pclip1->y2 - pclip1->y1);
  1480.                     if      (hh > 0.0)
  1481.                     {   cdir1 += pclip2->cdir;
  1482.                         fdir1 += pclip2->fdir;
  1483.                     }
  1484.                     else if (hh == 0.0)
  1485.                     {   cdir2 += pclip2->cdir;
  1486.                         fdir2 += pclip2->fdir;
  1487.                         if (pclip2->flag == 0)
  1488.                         {   pclip2->chain = pclipx;
  1489.                             pclipx = pclip2;
  1490.                         }
  1491.                     }
  1492.                 }
  1493.             }
  1494.  
  1495.             /* Horizontal lines only intersect the test line if they are
  1496.              * colinear with ours */
  1497.  
  1498.             else
  1499.                 if (pclip1->y1 == pclip1->y2 &&
  1500.                     pclip2->y1 == pclip2->y2 &&
  1501.                     pclip2->x1 == pclip1->x1)
  1502.                 {   cdir2 += pclip2->cdir;
  1503.                     fdir2 += pclip2->fdir;
  1504.                     if (pclip2->flag == 0)
  1505.                     {   pclip2->chain = pclipx;
  1506.                         pclipx = pclip2;
  1507.                     }
  1508.                 }
  1509.         }
  1510.  
  1511.         /* If the line is on the boundary of the intersection of the paths,
  1512.          * we keep it.  If it is interior to or on the boundary of the path
  1513.          * it does not belong to, or exterior to or on the boundary of the
  1514.          * other, we must have two or more coincident lines; we keep it and
  1515.          * its pair to preserve the degenerate path, discarding any others
  1516.          * that are also coincident.  Otherwise we discard it.  (We don't
  1517.          * preserve paths where both the clip and fill paths are
  1518.          * degenerate.)  Flag the lines for their ends to be swapped if they
  1519.          * are right or bottom edges */
  1520.  
  1521.         cdir2 = (((cdir1 + cdir2) & rule) != 0);
  1522.         fdir2 = (((fdir1 + fdir2) & rule) != 0);
  1523.         cdir1 = (( cdir1          & rule) != 0);
  1524.         fdir1 = (( fdir1          & rule) != 0);
  1525.  
  1526.         if ((cdir1 & fdir1) == (cdir2 & fdir2))
  1527.             if ((pclip1->fdir != 0 && (cdir1 | cdir2) && !(fdir1 & fdir2)) ||
  1528.                 (pclip1->cdir != 0 && (fdir1 | fdir2) && !(cdir1 & fdir2)))
  1529.             {   pclipx->flag = 2;           /* Keep its pair */
  1530.                 pclipx->swap = 1;           /* Swap one line */
  1531.                 pclipx = pclipx->chain;     /* Discard the rest */
  1532.             }
  1533.             else
  1534.             {   pclip1->flag = 1;           /* Discard the line */
  1535.                 clipflg++;
  1536.                 pclipx = NULL;              /* Leave the rest */
  1537.             }
  1538.         else
  1539.             if ((cdir1 & fdir1) != 0)
  1540.                 pclip1->swap = 1;           /* Swap right and bottom edges */
  1541.  
  1542.         while (pclipx)                      /* Discard the rest */
  1543.         {   pclipx->flag = 1;
  1544.             clipflg++;
  1545.             pclipx = pclipx->chain;
  1546.         }
  1547.     }
  1548.  
  1549.     /* Swap the lines so they are pointing in their proper directions */
  1550.  
  1551.     count1 = clipend;
  1552.     pclip1 = &cliparray[0];
  1553.     while (count1--)
  1554.     {   if (pclip1->swap) clipswap(pclip1);
  1555.         pclip1++;
  1556.     }
  1557.  
  1558.     /* Now join the lines back up to make the path.  The lines are in
  1559.      * approximate order of y2, so we optimise our search on that basis.
  1560.      * We start by picking any line; then we find the one that joins it */
  1561.  
  1562.     cliplength(0);
  1563.     point.type = ptmove;
  1564.     count = 0;
  1565.     step = 0;
  1566.     pathend = gstate.pathend;
  1567.  
  1568.     while (clipflg < clipend)
  1569.     {
  1570.         /* We step alternately backwards and forwards */
  1571.  
  1572.         count = count + step;
  1573.         if (step > 0)
  1574.             step = -step - 1;
  1575.         else
  1576.             step = -step + 1;
  1577.  
  1578.         /* When the array is half empty we compact it */
  1579.  
  1580.         if (clipflg + clipflg > clipend)
  1581.         {   count1 = 0;
  1582.             count2 = 0;
  1583.             while (count2 < clipend)
  1584.             {   if (count2 == count) count = count1;
  1585.                 pclip2 = clipptr[count2++];
  1586.                 if (pclip2->flag != 1) clipptr[count1++] = pclip2;
  1587.             }
  1588.             clipend -= clipflg;
  1589.             clipflg = 0;
  1590.             if (count >= clipend) count = clipend - 1;
  1591.             step = 1;
  1592.         }
  1593.  
  1594.         /* Search for a line that joins the current point */
  1595.  
  1596.         if (count >= 0 && count < clipend)
  1597.         {   pclip1 = clipptr[count];
  1598.             if (pclip1->flag != 1)
  1599.             {
  1600.                 /* At the beginning of a subpath add a move */
  1601.  
  1602.                 if (point.type == ptmove)
  1603.                 {   x1 = pclip1->x1;
  1604.                     y1 = pclip1->y1;
  1605.                     point.x = x1 / 256.0f;
  1606.                     point.y = y1 / 256.0f;
  1607.                     checkpathsize(pathend + 1);
  1608.                     patharray[pathend++] = point;
  1609.                     point.type = ptline;
  1610.                     xx = pclip1->x2;
  1611.                     yy = pclip1->y2;
  1612.                     step = 0;
  1613.                 }
  1614.  
  1615.                 /* Otherwise look for a line that joins the current point */
  1616.  
  1617.                 else if (pclip1->y1 == yy && pclip1->x1 == xx)
  1618.                 {   xx = pclip1->x2;
  1619.                     yy = pclip1->y2;
  1620.                     step = 0;
  1621.                 }
  1622.  
  1623.                 /* Found a line; if it returns to the beginning close the
  1624.                  * subpath */
  1625.  
  1626.                 if (step == 0)
  1627.                 {   pclip1->flag = 1;
  1628.                     clipflg++;
  1629.                     checkpathsize(pathend + 1);
  1630.                     point.x = xx / 256.0f;
  1631.                     point.y = yy / 256.0f;
  1632.                     if (yy == y1 && xx == x1)
  1633.                     {   point.type = ptclosex;
  1634.                         patharray[pathend++] = point;
  1635.                         point.type = ptmove;
  1636.                     }
  1637.                     else
  1638.                         patharray[pathend++] = point;
  1639.                     step = 1;
  1640.                 }
  1641.             }
  1642.         }
  1643.     }
  1644.  
  1645.     /* We now have the new clip path, at the end of the path.  To put the
  1646.      * clip path first, we first swap the order of the contents of the two
  1647.      * paths individually, then swap them both together */
  1648.  
  1649.     swappath(gstate.pathbeg, gstate.pathend);
  1650.     swappath(gstate.pathend, pathend);
  1651.     swappath(gstate.pathbeg, pathend);
  1652.     gstate.pathbeg = gstate.clipbeg + pathend - gstate.pathend;
  1653.     gstate.pathend = pathend;
  1654.     gstate.clipflag = 1;
  1655. }
  1656.  
  1657. /* Add a clip line to the array */
  1658.  
  1659. void clipline(struct clip *pclip)
  1660. {   struct clip *pc;
  1661.  
  1662.     if (pclip->x1 != pclip->x2 || pclip->y1 != pclip->y2)
  1663.     {   clipswap(pclip);
  1664.         checkclipsize(clipend + 1, clipend);
  1665.         pc = &cliparray[clipend];
  1666.         *pc = *pclip;
  1667.         clipptr[clipend++] = pc;
  1668.     }
  1669. }
  1670.  
  1671. /* Swap a clip line if necessary so y2 > y1 (or x2 > x1) */
  1672.  
  1673. void clipswap(struct clip *pclip)
  1674. {   int sw;
  1675.     if (pclip->swap ||
  1676.         pclip->y1 > pclip->y2 ||
  1677.            (pclip->y1 == pclip->y2 && pclip->x1 > pclip->x2))
  1678.     {   pclip->cdir = -pclip->cdir;
  1679.         pclip->fdir = -pclip->fdir;
  1680.         sw = pclip->x1;
  1681.         pclip->x1 = pclip->x2;
  1682.         pclip->x2 = sw;
  1683.         sw = pclip->y1;
  1684.         pclip->y1 = pclip->y2;
  1685.         pclip->y2 = sw;
  1686.     }
  1687. }
  1688.  
  1689. /* Swap the order of the points in a path */
  1690.  
  1691. void swappath(int beg, int end)
  1692. {   struct point point, *ppoint1, *ppoint2;
  1693.     ppoint1 = &patharray[beg];
  1694.     ppoint2 = &patharray[end];
  1695.     for (;;)
  1696.     {   ppoint2--;
  1697.         if (ppoint1 >= ppoint2) break;
  1698.         point = *ppoint1;
  1699.         *ppoint1 = *ppoint2;
  1700.         *ppoint2 = point;
  1701.         ppoint1++;
  1702.     }
  1703. }
  1704.  
  1705. /* End of file "postgraph.c" */
  1706.